package com.example.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Leetcode94_BianLiTree {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        root.right.right.left = new TreeNode(6);

        afterOrderTraversal2(root).forEach(x -> {
            System.out.print(x + ", ");
        });

        System.out.println("\n" + root.val + "," + root.left.val);

    }

    /**
     * 前序遍历(迭代实现)
     *
     *
     * @param root
     * @return
     */
    public static List<Integer> beforeOrderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();

        while (root != null || !stack.isEmpty()) {

            while (root != null) {//一直往左走
                stack.push(root);
                res.add(root.val);
                root = root.left;
            }

            root = stack.pop();
            root = root.right;

        }
        return res;
    }

    /**
     * 中序遍历(迭代实现)
     *
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();

        while (root != null || !stack.isEmpty()) {

            while (root != null) {//一直往左走
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            res.add(root.val);
            root = root.right;

        }
        return res;
    }

    /**
     * 后序遍历(迭代实现)
     *
     *
     * @param root
     * @return
     */
    public static List<Integer> afterOrderTraversal2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        TreeNode node = root;
        TreeNode prev = null;// prev用于记录上次访问打印的节点
        while(node != null || !stack.isEmpty()){
            while(node != null){
                //访问左子树
                stack.push(node);
                node = node.left;
            }
            //判断栈顶元素(根)
            node = stack.peek();

            if(node.right == null || node.right == prev){ // 此时的根的右子树为空或者根的右子树已经访问过了
                // 访问根节点，并出栈，将打印过的节点从栈中删除
                stack.pop();
                res.add(node.val);
                //记录prev，表示以当前prev为根的子树已经访问过了
                prev = node;
                // node置null就不会再次访问以node为根节点的左右子树，这里的node既然已经打印，说明它的左右子树早已访问完毕
                node = null;
            }else{
                //访问右子树
                node = node.right;
            }
        }
        return res;
    }


    /**
     * 前中后序遍历二叉树(递归)
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
//        beforeOrderTraversalByRecursion(root, res);
        inorderTraversalByRecursion(root, res);
//        afterOrderTraversalByRecursion(root, res);
        return res;
    }

    /**
     * 前序递归实现
     * @param root
     * @param resultList
     */
    private static void beforeOrderTraversalByRecursion(TreeNode root, List<Integer> resultList) {
        if (root == null)
            return;

        resultList.add(root.val);
        inorderTraversalByRecursion(root.left, resultList);
        inorderTraversalByRecursion(root.right, resultList);
    }

    /**
     * 中序递归实现
     * @param root
     * @param resultList
     */
    private static void inorderTraversalByRecursion(TreeNode root, List<Integer> resultList) {
        if (root == null)
            return;

        inorderTraversalByRecursion(root.left, resultList);
        resultList.add(root.val);
        inorderTraversalByRecursion(root.right, resultList);
    }

    /**
     * 后序递归实现
     * @param root
     * @param resultList
     */
    private static void afterOrderTraversalByRecursion(TreeNode root, List<Integer> resultList) {
        if (root == null)
            return;

        inorderTraversalByRecursion(root.left, resultList);
        inorderTraversalByRecursion(root.right, resultList);
        resultList.add(root.val);
    }
}
